UVa/11116 - Babel towers/11116.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4
   5 using namespace std;
   6
   7 typedef long long ll;
   8 typedef pair<ll, ll> point;
   9 typedef pair<point, ll> disc;
  10
  11
  12 inline ll distsqr(const point &a, const point &b){
  13   return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
  14 }
  15
  16
  17 int main(){
  18   int n;
  19   while (scanf("%d", &n) && (n > 0)){
  20
  21     vector<disc> d(n);
  22     for (int i=0; i<n; ++i){
  23       ll x, y, r;
  24       cin >> x >> y >> r;
  25       d[i] = disc(point(x,y), r);
  26     }
  27
  28     int k;
  29     bool ok = true;
  30     for (int i=1; i < n && ok; ++i){
  31       for (int j=0; j<i && ok; ++j){
  32         if (distsqr(d[i].first, d[j].first) >= (d[j].second * d[j].second)){
  33           ok = false;
  34           k = i;
  35         }
  36       }
  37     }
  38
  39     cout << (ok?"F":"Unf") << "easible";
  40     if (!ok) cout << " " << k;
  41     cout << endl;
  42
  43   }
  44   return 0;
  45 }